/*
 * One example for NOI CSP-J Lesson 10:
 * <https://courses.fmsoft.cn/plzs/noijunior-csp-exercises-lower.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <vector>
#include <iostream>
#include <cassert>

using namespace std;

size_t counting_zero_pairs_naive(const vector<int> &a)
{
    size_t ans = 0;
    size_t n = a.size();

    for (size_t i = 0; i < n; i++)
        for (size_t j = 0; j < n; j++)
            if (a[i] + a[j] == 0)
                ans++;

    return ans;
}

size_t counting_zero_pairs_shrewd(const vector<int> &a)
{
    size_t ans = 0;
    size_t n = a.size();

    for (size_t i = 0; i < n; i++)
        for (size_t j = 0; j < i; j++)
            if (a[i] + a[j] == 0)
                ans++;

    ans *= 2;
    return ans;
}

// maxv 应是所有可能取值的绝对值之最大值。
size_t counting_zero_pairs_insightful(const vector<int> &a, int maxv)
{
    // all_possible_values 中保存的是 [-maxv, maxv] 区间的数是否
    // 出现在数组 a 中的标志。初始为均不在数组中。
    vector<bool> all_possible_values(maxv * 2 + 1, false);

    size_t ans = 0;
    size_t n = a.size();
    for (size_t i = 0; i < n; i++) {

        // 如果 all_possible_values 中存在 a[i] 的相反数，则 ans 递增。
        if (all_possible_values[maxv - a[i]])
            ++ans;

        // 在 all_possible_values 中设置 a[i] 存在。
        all_possible_values[maxv + a[i]] = true;
    }

    ans *= 2;
    return ans;
}

int main() {
    vector<int> a = { -1, 2, 1, -3 };
    size_t expected = 2;

    size_t got = counting_zero_pairs_naive(a);
    assert(got == expected);

    got = counting_zero_pairs_shrewd(a);
    assert(got == expected);

    got = counting_zero_pairs_insightful(a, 10);
    assert(got == expected);
    cout << got << endl;

    return 0;
}

